// https://www.lintcode.com/problem/topological-sorting/description

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    
    // 法一：bfs 
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
        vector<DirectedGraphNode*> res;
        map<DirectedGraphNode*, int> rec;
        deque<DirectedGraphNode*> q;
        for (DirectedGraphNode* node: graph)
        {
            for (DirectedGraphNode* n: node->neighbors)
            {
                rec[n]++;
            }
        }
        for (DirectedGraphNode* node: graph) 
        {
            if (rec.find(node) == rec.end()) //度为0的加入
                q.push_back(node);
        }
        while (!q.empty())
        {
            DirectedGraphNode* tmp = q.front();
            q.pop_front();
            res.push_back(tmp);
            for (DirectedGraphNode* n: tmp->neighbors)
            {
                rec[n]--;
                if (rec[n] == 0)
                    q.push_back(n);
            }
        }
        return res;
    }
     
    // 法二：dfs
    // void dfs(DirectedGraphNode* node, vector<DirectedGraphNode*>& res, set<DirectedGraphNode*>& s)
    // {
    //     if (s.find(node) != s.end())
    //         return;
    //     s.insert(node);
    //     for (DirectedGraphNode* n: node->neighbors)
    //     {
    //         dfs(n, res, s);
    //     }
    //     // res.push_back(node);
    //     res.insert(res.begin(), node);
    // }
    // vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
    //     vector<DirectedGraphNode*> res;
    //     set<DirectedGraphNode*> s;
    //     for (DirectedGraphNode* node: graph)
    //     {
    //         dfs(node, res, s);
    //     }
    //     return res;
    // }
};